package class10;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * https://leetcode.cn/problems/ZL6zAn/
 * 求岛屿问题
 * 题目：
 * 给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。
 * 一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
 * 岛屿如下：
 * >    001010
 * >    111010
 * >    100100
 * >    000000
 * 有三个岛：
 * 第一个    第二个    第三个
 * + 001     1
 * + 111     1       00100
 * + 100     0
 * 解题思路：
 * 1.遍历矩阵，计算进行感染
 * 并行算法：
 *
 */
public class Code04_islandArea {
    public static void main(String[] args) {
        int[][] matrix = {
                {0, 0, 1, 0, 1, 0},
                {1, 1, 1, 0, 1, 0},
                {1, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0}
        };
        int land = isLand(matrix);
        System.out.println(land);
    }

    public static int isLand(int[][] matrix) {
        if (matrix == null) {
            return 0;
        }
        int row = matrix.length; // 行数
        int col = matrix[0].length; // 列数
        int res = 0;
        int max = 0;
        /**
         * 遍历绝阵
         */
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 当遍历到 1 时，需要进行感染
                if (matrix[i][j] == 1) {
                    res++; // 计算岛屿数量
                    int area = infect(matrix, i, j, row, col); // 计算岛屿面积
                    max = Math.max(area, max); // 计算最大岛屿面积
                }
            }
        }
        return res;
    }

    public static int infect(int[][] m, int i, int j, int row, int col) {
        if (i < 0 || i >= row || j < 0 || j >= col || m[i][j] != 1) {
            return 0;
        }
        m[i][j] = 2; // 将遍历过的岛，改成2
        int area = 1; //存在岛屿1
        area += infect(m, i - 1, j, row, col);
        area += infect(m, i + 1, j, row, col);
        area += infect(m, i, j - 1, row, col);
        area += infect(m, i, j + 1, row, col);
        return area;
    }
}
